SherbyNet - /page/wikibook/entry.mu

Micron Document

Nonlinear conjugate gradient method

11.8 KB · ⇊ 7 parts · ⤓ Micron 11.8 KB · ⤓ HTML 85.6 KB

──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────

top

In numerical optimization, the nonlinear conjugate gradient method generalizes the conjugate gradient method to nonlinear optimization. For a quadratic function f ( x ) {\displaystyle \displaystyle f(x)}

f ( x ) = ‖ ‖ A x − − b ‖ ‖ 2 , {\displaystyle \displaystyle f(x)=\|Ax-b\|^{2},}

the minimum of f {\displaystyle f} is obtained when the gradient is 0:

∇ ∇ x f = 2 A T ( A x − − b ) = 0 {\displaystyle \nabla _{x}f=2A^{T}(Ax-b)=0} .

Whereas linear conjugate gradient seeks a solution to the linear equation A T A x = A T b {\displaystyle \displaystyle A^{T}Ax=A^{T}b} , the nonlinear conjugate gradient method is generally used to find the local minimum of a nonlinear function using its gradient ∇ ∇ x f {\displaystyle \nabla _{x}f} alone. It works when the function is approximately quadratic near the minimum, which is the case when the function is twice differentiable at the minimum and the second derivative is non-singular there.

Given a function f ( x ) {\displaystyle \displaystyle f(x)} of N {\displaystyle N} variables to minimize, its gradient ∇ ∇ x f {\displaystyle \nabla _{x}f} indicates the direction of maximum increase. One simply starts in the opposite (steepest descent) direction:

Δ Δ x 0 = − − ∇ ∇ x f ( x 0 ) {\displaystyle \Delta x_{0}=-\nabla _{x}f(x_{0})}

with an adjustable step length α α {\displaystyle \displaystyle \alpha } and performs a line search in this direction until it reaches the minimum of f {\displaystyle \displaystyle f} :

α α 0 := arg ⁡ ⁡ min α α f ( x 0 + α α Δ Δ x 0 ) {\displaystyle \displaystyle \alpha _{0}:=\arg \min _{\alpha }f(x_{0}+\alpha \Delta x_{0})} , x 1 = x 0 + α α 0 Δ Δ x 0 {\displaystyle \displaystyle x_{1}=x_{0}+\alpha _{0}\Delta x_{0}}

After this first iteration in the steepest direction Δ Δ x 0 {\displaystyle \displaystyle \Delta x_{0}} , the following steps constitute one iteration of moving along a subsequent conjugate direction s n {\displaystyle \displaystyle s_{n}} , where s 0 = Δ Δ x 0 {\displaystyle \displaystyle s_{0}=\Delta x_{0}} :

1. Calculate the steepest direction: Δ Δ x n = − − ∇ ∇ x f ( x n ) {\displaystyle \Delta x_{n}=-\nabla _{x}f(x_{n})} ,

2. Compute β β n {\displaystyle \displaystyle \beta _{n}} according to one of the formulas below,

3. Update the conjugate direction: s n = Δ Δ x n + β β n s n − − 1 {\displaystyle \displaystyle s_{n}=\Delta x_{n}+\beta _{n}s_{n-1}}

4. Perform a line search: optimize α α n = arg ⁡ ⁡ min α α f ( x n + α α s n ) {\displaystyle \displaystyle \alpha _{n}=\arg \min _{\alpha }f(x_{n}+\alpha s_{n})} ,

5. Update the position: x n + 1 = x n + α α n s n {\displaystyle \displaystyle x_{n+1}=x_{n}+\alpha _{n}s_{n}} ,

With a pure quadratic function the minimum is reached within N iterations (excepting roundoff error), but a non-quadratic function will make slower progress. Subsequent search directions lose conjugacy requiring the search direction to be reset to the steepest descent direction at least every N iterations, or sooner if progress stops. However, resetting every iteration turns the method into steepest descent. The algorithm stops when it finds the minimum, determined when no progress is made after a direction reset (i.e. in the steepest descent direction), or when some tolerance criterion is reached.

Within a linear approximation, the parameters α α {\displaystyle \displaystyle \alpha } and β β {\displaystyle \displaystyle \beta } are the same as in the linear conjugate gradient method but have been obtained with line searches. The conjugate gradient method can follow narrow (ill-conditioned) valleys, where the steepest descent method slows down and follows a criss-cross pattern.

Four of the best known formulas for β β n {\displaystyle \displaystyle \beta _{n}} are named after their developers:

• Fletcher–Reeves:cite-ref-1[1]

β β n F R = Δ Δ x n T Δ Δ x n Δ Δ x n − − 1 T Δ Δ x n − − 1 . {\displaystyle \beta _{n}^{FR}={\frac {\Delta x_{n}^{T}\Delta x_{n}}{\Delta x_{n-1}^{T}\Delta x_{n-1}}}.}

• Polak–Ribière:cite-ref-2[2]

β β n P R = Δ Δ x n T ( Δ Δ x n − − Δ Δ x n − − 1 ) Δ Δ x n − − 1 T Δ Δ x n − − 1 . {\displaystyle \beta _{n}^{PR}={\frac {\Delta x_{n}^{T}(\Delta x_{n}-\Delta x_{n-1})}{\Delta x_{n-1}^{T}\Delta x_{n-1}}}.}

• Hestenes–Stiefel:cite-ref-3[3]

β β n H S = Δ Δ x n T ( Δ Δ x n − − Δ Δ x n − − 1 ) − − s n − − 1 T ( Δ Δ x n − − Δ Δ x n − − 1 ) . {\displaystyle \beta _{n}^{HS}={\frac {\Delta x_{n}^{T}(\Delta x_{n}-\Delta x_{n-1})}{-s_{n-1}^{T}(\Delta x_{n}-\Delta x_{n-1})}}.}

• Dai–Yuan:cite-ref-4[4]

β β n D Y = Δ Δ x n T Δ Δ x n − − s n − − 1 T ( Δ Δ x n − − Δ Δ x n − − 1 ) . {\displaystyle \beta _{n}^{DY}={\frac {\Delta x_{n}^{T}\Delta x_{n}}{-s_{n-1}^{T}(\Delta x_{n}-\Delta x_{n-1})}}.} .

These formulas are equivalent for a quadratic function, but for nonlinear optimization the preferred formula is a matter of heuristics or taste. A popular choice is β β = max { 0 , β β P R } {\displaystyle \displaystyle \beta =\max\{0,\beta ^{PR}\}} , which provides a direction reset automatically.cite-ref-5[5]

Algorithms based on Newton's method potentially converge much faster. There, both step direction and length are computed from the gradient as the solution of a linear system of equations, with the coefficient matrix being the exact Hessian matrix (for Newton's method proper) or an estimate thereof (in the quasi-Newton methods, where the observed change in the gradient during the iterations is used to update the Hessian estimate). For high-dimensional problems, the exact computation of the Hessian is usually prohibitively expensive, and even its storage can be problematic, requiring O ( N 2 ) {\displaystyle O(N^{2})} memory (but see the limited-memory L-BFGS quasi-Newton method).

The conjugate gradient method can also be derived using optimal control theory.cite-ref-0-6-0[6] In this accelerated optimization theory, the conjugate gradient method falls out as a nonlinear optimal feedback controller,

u = k ( x , x ˙ ˙ ) := − − γ γ a ∇ ∇ x f ( x ) − − γ γ b x ˙ ˙ {\displaystyle u=k(x,{\dot {x}}):=-\gamma _{a}\nabla _{x}f(x)-\gamma _{b}{\dot {x}}}

for the double integrator system,

x ¨ ¨ = u {\displaystyle {\ddot {x}}=u}

The quantities γ γ a > 0 {\displaystyle \gamma _{a}>0} and γ γ b > 0 {\displaystyle \gamma _{b}>0} are variable feedback gains.cite-ref-0-6-1[6]

Contents

• See also

• References